package com.example.demo.suanfa_heap;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @program: java_base
 * @description: 最大覆盖线段数
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/16 14:50
 */
public class CoverMaxDemo {


    /**
     * 1.对 lines 按照start排序，升序
     * 2.建立小根堆
     * 3.向堆内添加元素，要求如下：
     *  3.1 堆内保留 end 位置变量
     *  3.2 比较堆内 是否有比需要添加元素大的 start？有弹出，没有add入此次end
     *  3.3 记录最大值
     *
     *  why  ?
     *      数组以开始节点维持 升序
     *      堆  小根堆
     *      堆内维持着  大于(不包含等于) 当前开始节点的 所有结束位置 ，顾heap.size() 为当前线段最多的线段数
     *
     *      1.进入堆的规则：先比较要进入的while( startIndex < heap.peek() ？ heap.pop: insert end Index)
     *      2.每次结束1步骤后，heap.size() 就是当前线段包含的重合线段数
     *      因为：在heap内是比当前线段开始位置大的 结尾数量！顾推导出
     *
     */
    @Test
    public void maxCover() {
        int maxCount = 0;
        Line[] lines = {
                new Line(2,100),
                new Line(2,234),
                new Line(4,7),
                new Line(7,9),
                new Line(12,21),
        };
        Arrays.sort(lines,new LineComparator());

        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(lines[0].end);
        for (int i = 1; i < lines.length; i++) {
            Line line = lines[i];
            while (line.start >= heap.peek() && !heap.isEmpty()){
                heap.poll();
            }
            heap.add(line.end);
//            maxCount = maxCount > heap.size() ? maxCount : heap.size();
            maxCount = Math.max(maxCount,heap.size());
        }
        System.out.println(maxCount);
    }

    class Line {
        public int start;
        public int end;
        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    class LineComparator implements Comparator<Line> {
        @Override
        public int compare(Line o1, Line o2) {
            return o1.start - o2.start;
        }
    }
}
